package cn.zzf.algs.note.base.sort;

import cn.zzf.algs.note.base.util.MathUtil;
import cn.zzf.algs.note.base.util.SortUtil;

import java.util.Arrays;

/**
 * @author GaoFeng2017
 * @date 2020/6/18 17:33
 */
public class ShellSort implements Sort {

    /**
     * 希尔排序，使用h增量
     */
    @Override
    public void sort(Comparable[] elements) {
        // 通过增量h来对交换不相邻的元素进行排序，当h等于1时，使用插入排序来进行排序，减少了元素交换的次数

        // 生成h增量, 增量公式(3^k - 1) / 2, h < N/3
        // 1, 1
        // 2, 4
        // 3,13

        if (elements.length < 2) {
            return;
        }

        // 计算增量，并存入数组中
        int incrementsLength = (int) MathUtil.log(elements.length, 3) + 1;
        System.out.println("增量数组长度" + incrementsLength + " , " + elements.length);

        Integer[] increments = new Integer[incrementsLength];

        increments[0] = 1;

        for (int i = 1; i < increments.length; i++) {
            increments[i] = 3 * increments[i - 1] + 1;
        }

        System.out.println("增量数组：" + Arrays.toString(increments));

        // 排序
        for (int k = increments.length - 1; k >= 0; k--) {
            int increment = increments[k];
            for (int i = increment; i < elements.length; i++) {
                /*System.out.println("增量为" + increment);
                System.out.println(Arrays.toString(elements));*/
                for (int j = i; j >= increment && SortUtil.less(elements[j], elements[j - increment]); j -= increment) {
                    SortUtil.exchange(elements, j, j - increment);
                }
            }
        }

        // 重点：增量是为了减少交换的次数。

    }


}